#ifndef RBTREE_H
#define RBTREE_H
#include <stdio.h>  
#include <stdlib.h>  
typedef enum { RED, BLACK } Color;  

typedef struct RBTreeNode {  
    void *key;                 // 键  
    void *value;               // 值 (对于 Set 可为 NULL)  
    Color color;               // 颜色  
    struct RBTreeNode *left;   // 左子树  
    struct RBTreeNode *right;  // 右子树  
    struct RBTreeNode *parent; // 父节点  
} RBTreeNode;  
typedef struct {  
    RBTreeNode *root; // 根节点  
    int (*compare)(const void *, const void *); // 比较函数  
    int size; // 节点数量
} RBTree;  
typedef struct {  
    void **key; // 存储指向元素的指针  
    void **value; // 存储指向元素的指针  
    int size;     // 数组大小  
} Array; 
RBTreeNode* create_node(void *key, void *value);
void left_rotate(RBTree *tree, RBTreeNode *x);
void right_rotate(RBTree *tree, RBTreeNode *y);
void fix_violation(RBTree *tree, RBTreeNode *node);
void RB_insert(RBTree *tree, void *key, void *value);
RBTreeNode* search(RBTree *tree, void *key);
void fix_double_black(RBTree *tree, RBTreeNode *x);
void delete_node(RBTree *tree, void *key);
void inorder_traversal(RBTreeNode *node, Array *array, int *index);
Array* tree_to_array(RBTree *tree);
#endif